﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Collections;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.IO;

namespace TSP
{
  
    [Serializable]
    public class Chromosome : ICloneable
    {        
        public int[] chromo;
        private float _fitness;
        private int _chromoLength = 1;
        private float _costOfTour;

        public delegate float CaculateDistance(int city1, int city2);
        public CaculateDistance calDistance;

        public float Fitness
        {
            get { return _fitness; }
            set { _fitness = value; }
        }

        public float CostOfTour
        {
            get { return _costOfTour; }
            set { _costOfTour = value; }
        }

        public int ChromoLength
        {
            get { return _chromoLength; }
            set { _chromoLength = value; }
        }        

        public Chromosome()
        {

        }

        public Chromosome(int length)
        {
            _chromoLength = length;
            chromo = new int[length];
        }

        public object Clone()
        {
            //return this.MemberwiseClone();
            using (MemoryStream ms = new MemoryStream())
            {
                IFormatter bf = new BinaryFormatter();
                bf.Serialize(ms, this);
                ms.Position = 0;
                return bf.Deserialize(ms);
            }
        }
        
        public void createRandomChrome(Random ran)
        {
            //int currentLength = _chromoLength;
            int[] tourTemp = new int[_chromoLength];            
            for (int i = 1; i <= _chromoLength; i++)
            {
                tourTemp[i - 1] = i;
            }                 
            int count = _chromoLength;            
            int pos = 0;            
            for(int i = 0; i < _chromoLength - 2; i++)
            {                          
                pos = ran.Next(count);         
                this.chromo[i]=tourTemp[pos];
                for(int j = pos; j < count-1; j++)
                {
                    tourTemp[j]=tourTemp[j+1];
                }
                count--;
            }
            this.chromo[_chromoLength-1] = tourTemp[1];
            this.chromo[_chromoLength-2] = tourTemp[0];         
        }

        public void mutation(Random ran)
        {           
            for (int i=0; i < InOutData.NumOfCity; i++)
            {
                if (ran.NextDouble() < Population.MutationRate)
                    {
                        int pos1 = i;//= ran.Next(_chromoLength);
                        int pos2 = ran.Next(_chromoLength);            
                        int temp = this.chromo[pos1];
                        this.chromo[pos1] = this.chromo[pos2];
                        this.chromo[pos2] = temp;
                }
            }
        }
        
        private void inversionSegment(int p1, int p2, ref int[] arr)
        {            
            if (p1 <= p2)
            {
                int tg = 0;
                int i, j;
                for(i = p1,j = p2; i<=(p1 + p2)/2; i++, j--)
                {
                    tg = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tg;
                }                
            }
            else
            {
                int tg = 0;
                int i, j;
                for (i = p2, j = p1; i <= (p1 + p2) / 2; i++, j--)
                {
                    tg = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tg;
                }
            }
        }

        public void inversionMutation(Random ran)
        {
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                if (ran.NextDouble() < Population.MutationRate)
                {
                    int pos1 = ran.Next(_chromoLength);
                    int pos2 = ran.Next(_chromoLength);
                    inversionSegment(pos1, pos2, ref this.chromo);
                }
            }
        }

        public void orderCrossover(Chromosome chromo2, out Chromosome child1, out Chromosome child2, Random ran)
        {
            child1 = new Chromosome(InOutData.NumOfCity);
            child2 = new Chromosome(InOutData.NumOfCity);           
            int pos1 = ran.Next(_chromoLength - 1);            
            int pos2 = ran.Next(_chromoLength - pos1) + pos1;            
            ArrayList s1 = new ArrayList();
            ArrayList s2 = new ArrayList();
            for (int i = pos1; i <= pos2; i++)
            {
                child1.chromo[i] = this.chromo[i];
                s1.Add(this.chromo[i]);
                child2.chromo[i] = chromo2.chromo[i];
                s2.Add(chromo2.chromo[i]);
            }                        
            int index1 = 1;
            int index2 = 1;
            int temp = 0;
            for (int i = 1; i <= _chromoLength; i++) //for (int i = pos2+1; i < pos2 + this.chromoLength - (pos2 - pos1 + 1); i++)
            {
                temp = i + pos2;
                if (temp >= _chromoLength)
                {
                    temp = temp - _chromoLength;
                }
                int ps1 = index1 + pos2;
                if (ps1 >= _chromoLength)
                {
                    ps1 = ps1 - _chromoLength;
                }
                int ps2 = index2 + pos2;
                if (ps2 >= _chromoLength)
                {
                    ps2 = ps2 - _chromoLength;
                }
                if (!s1.Contains(chromo2.chromo[temp]))
                {
                    child1.chromo[ps1] = chromo2.chromo[temp];
                    index1++;
                }
                if (!s2.Contains(this.chromo[temp]))
                {
                    child2.chromo[ps2] = this.chromo[temp];
                    index2++;
                }                              
            }
            //for (int i = 0; i < _chromoLength; i++)
            //    Console.Write(child1.chromo[i] + " ");
            //Console.WriteLine();
        }

        public void modifiedOrderCrossover(Chromosome chromo2, out Chromosome child1, out Chromosome child2, Random ran)
        {
            child1 = new Chromosome(InOutData.NumOfCity);
            child2 = new Chromosome(InOutData.NumOfCity);
            int pos1 = ran.Next(_chromoLength - 1);
            int pos2 = ran.Next(_chromoLength - pos1) + pos1;
            ArrayList s1 = new ArrayList();
            ArrayList s2 = new ArrayList();
            for (int i = pos1; i <= pos2; i++)
            {
                child1.chromo[i] = this.chromo[i];
                s1.Add(this.chromo[i]);
                child2.chromo[i] = chromo2.chromo[i];
                s2.Add(chromo2.chromo[i]);
            }
            int index1 = 1;
            int index2 = 1;
            int temp = 0;
            for (int i = 1; i <= _chromoLength; i++) 
            {
                temp = i + pos2;
                if (temp >= _chromoLength)
                {
                    temp = temp - _chromoLength;
                }
                int ps1 = index1 + pos2;
                if (ps1 >= _chromoLength)
                {
                    ps1 = ps1 - _chromoLength;
                }
                int ps2 = index2 + pos2;
                if (ps2 >= _chromoLength)
                {
                    ps2 = ps2 - _chromoLength;
                }
                if (!s1.Contains(chromo2.chromo[temp]))
                {
                    child1.chromo[ps1] = chromo2.chromo[temp];
                    index1++;
                }
                if (!s2.Contains(this.chromo[temp]))
                {
                    child2.chromo[ps2] = this.chromo[temp];
                    index2++;
                }
            }
            if (pos1 >= 2)
            {
                inversionSegment(0, pos1 - 1, ref child1.chromo);
                inversionSegment(0, pos1 - 1, ref child2.chromo);
            }
            if (pos2 + 1 == (_chromoLength - 1))
            {
                inversionSegment(pos2 + 1, _chromoLength - 1, ref child1.chromo);
                inversionSegment(pos2 + 1, _chromoLength - 1, ref child2.chromo);
            }
            
            
        }

        private int findNextCity(int city, int[] tour)
        {
            int t = 0;
            for (int i = 0; i < _chromoLength; i++)
            {
                if (tour[i] == city)
                {
                    if (i == _chromoLength - 1)
                    {
                        break;
                    }
                    else
                    {
                        t = tour[i + 1];
                        break;
                    }
                }
            }
            return t;
        }

        public void sequentialContructiveCrossover(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bit = new bool[_chromoLength];
            int nextCt1, nextCt2;

            for (int i = 0; i < _chromoLength; i++)
            {
                bit[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);
            child.chromo[0] = this.chromo[0];
            bit[this.chromo[0] - 1] = true;

            for (int i = 1; i < _chromoLength; i++)
            {
                nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                if (nextCt1 == 0 || bit[nextCt1 - 1])
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bit[j])
                        {
                            nextCt1 = j + 1;
                            break;
                        }

                    }
                }
                if (nextCt2 == 0 || bit[nextCt2 - 1])
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bit[j])
                        {
                            nextCt2 = j + 1;
                            break;
                        }

                    }
                }
                if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                {
                    child.chromo[i] = nextCt1;
                    bit[nextCt1 - 1] = true;
                }
                else
                {
                    child.chromo[i] = nextCt2;
                    bit[nextCt2 - 1] = true;
                }
            }//for


        }

        public void modifiedSequentialContructiveCrossover(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bit = new bool[_chromoLength];
            int nextCt1, nextCt2;

            for (int i = 0; i < _chromoLength; i++)
            {
                bit[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);

            if (this._fitness < chromo2._fitness)
            {
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;
            }
            else
            {             
                child.chromo[0] = chromo2.chromo[0];
                bit[chromo2.chromo[0] - 1] = true;
            }          
           
            for (int i = 1; i < _chromoLength; i++)
            {
                nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                if (nextCt1 == 0 || bit[nextCt1 - 1])
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bit[this.chromo[j]-1])
                        {
                            nextCt1 = this.chromo[j];
                            break;
                        }
                    }
                }
                if (nextCt2 == 0 || bit[nextCt2 - 1])
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bit[chromo2.chromo[j]-1])
                        {
                            nextCt2 = chromo2.chromo[j];
                            break;
                        }
                    }
                }

                if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                {
                    child.chromo[i] = nextCt1;
                    bit[nextCt1 - 1] = true;
                }
                else
                {
                    child.chromo[i] = nextCt2;
                    bit[nextCt2 - 1] = true;
                }
            }//for


        }        

        public float caculateCostOfTour()
        {
            float s = 0;
            for (int i = 0; i < _chromoLength - 1; i++)
            {
                s = s + this.calDistance(this.chromo[i] - 1, this.chromo[i + 1] - 1);
            }
            s = s + this.calDistance(this.chromo[_chromoLength - 1] - 1, this.chromo[0] - 1);
            return s;        
        }

        public void calculateFitness(float maxCost)
        {
            _costOfTour = this.caculateCostOfTour();
            this._fitness = _costOfTour;//maxCost - _costOfTour;
            if ((Population.BestChromosome == null) || (this._fitness < Population.BestChromosome.Fitness))
            {
                Population.BestChromosome = (Chromosome)this.Clone();               
            }
        }       
        
        //Modify: search all element
        //Find city in chrome[] has min distance to ct
        private int findMinCity(int currentCity, int[] chrome, bool[] bit)
        {
            int minCt = -1;
            float minDistance = float.MaxValue;

            for (int j = 0; j < _chromoLength; j++)
            {
                if (!bit[chromo[j] - 1])
                {
                    //if(chrome[j]!=currentCity)
                    //{
                        if(calDistance(currentCity - 1, chromo[j] - 1) < minDistance)
                        {
                            minDistance = calDistance(currentCity - 1, chromo[j] - 1);
                            minCt = chromo[j];
                        }
                    //}
                }
            }
            return minCt;
        }

        //Crossover: find city has min distance in chrome
        public void M_MSCX(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bitFlag = new bool[_chromoLength];
            int nextCt1, nextCt2;
            //store the city having distance to current city in subtour is minimun
            int minCity1, minCity2;

            for (int i = 0; i < _chromoLength; i++)
            {
                bitFlag[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);
            child.chromo[0] = this.chromo[0];
            bitFlag[this.chromo[0] - 1] = true;

            for (int i = 1; i < _chromoLength; i++)
            {
                nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                if (nextCt1 == 0 || bitFlag[nextCt1 - 1])
                {
                    nextCt1 = findMinCity(child.chromo[i - 1], this.chromo, bitFlag);
                }
                if (nextCt2 == 0 || bitFlag[nextCt2 - 1])
                {
                    nextCt2 = findMinCity(child.chromo[i - 1], chromo2.chromo, bitFlag);
                }

                if (calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                {
                    child.chromo[i] = nextCt1;
                    bitFlag[nextCt1 - 1] = true;
                }
                else
                {
                    child.chromo[i] = nextCt2;
                    bitFlag[nextCt2 - 1] = true;
                }
            }//for


        }

        //Crossover: find before and after the current city
        //method find before and after the current city are 
        public int findBeforeAfterCity(int currentCity, int[] chrome, bool[] bit)
        {
            int minCity = -1;
            for (int i = 0; i < _chromoLength; i++)
            {
                if (chrome[i] == currentCity)
                {
                    if (i == _chromoLength - 1)
                    {
                        if (!bit[chrome[_chromoLength - 2] - 1])
                        {
                            minCity = chrome[_chromoLength - 2];
                        }
                    }
                    else
                    {
                        if (i == 0)
                        {
                            if (!bit[chrome[1] - 1] && !bit[chrome[_chromoLength - 1] - 1])
                            {
                                if (calDistance(currentCity - 1, chrome[1] - 1) < calDistance(currentCity - 1, chrome[_chromoLength - 1] - 1))
                                {
                                    minCity = chrome[1];
                                }
                                else
                                {
                                    minCity = chrome[_chromoLength - 1];
                                }
                            }
                            else
                            {
                                if (!bit[chrome[1] - 1])
                                {
                                    minCity = chrome[1];
                                }
                                if (!bit[chrome[_chromoLength - 1] - 1])
                                {
                                    minCity = chrome[_chromoLength - 1];
                                }
                            }
                        }
                        else
                        {
                            if (!bit[chrome[i + 1] - 1] && !bit[chrome[i - 1] - 1])
                            {
                                if (calDistance(currentCity - 1, chrome[i + 1] - 1) < calDistance(currentCity - 1, chrome[i - 1] - 1))
                                {
                                    minCity = chrome[i + 1];
                                }
                                else
                                {
                                    minCity = chrome[i - 1];
                                }
                            }
                            else
                            {
                                if (!bit[chrome[i + 1] - 1])
                                {
                                    minCity = chrome[i + 1];
                                }
                                if (!bit[chrome[i - 1] - 1])
                                {
                                    minCity = chrome[i - 1];
                                }
                            }
                        }
                    }
                    break;
                }// if (chrome[i] == currentCity)
            }//for
            return minCity;
        }

        //Tim thanh pho co canh toi thanh pho hien nho nhat
        public int findBeforeAfterCity1(int currentCity, int[] chrome, bool[] bit)
        {
            int minCity = -1;
            for (int i = 0; i < _chromoLength; i++)
            {
                if (chrome[i] == currentCity)
                {
                    if (i == _chromoLength - 1)
                    {                       
                        if (!bit[chrome[_chromoLength - 2] - 1] && !bit[chrome[0] - 1])
                        {
                            if (calDistance(currentCity - 1, chrome[_chromoLength - 2] - 1) < calDistance(currentCity - 1, chrome[0] - 1))
                            {
                                minCity = chrome[_chromoLength - 2];
                            }
                            else
                            {
                                minCity = chrome[0];
                            }
                        }
                        else
                        {
                            if (!bit[chrome[0] - 1])
                            {
                                minCity = chrome[0];
                            }
                            if (!bit[chrome[_chromoLength - 2] - 1])
                            {
                                minCity = chrome[_chromoLength - 2];
                            }
                        }
                    }
                    else
                    {
                        if (i == 0)
                        {
                            if (!bit[chrome[1] - 1] && !bit[chrome[_chromoLength - 1] - 1])
                            {
                                if (calDistance(currentCity - 1, chrome[1] - 1) < calDistance(currentCity - 1, chrome[_chromoLength - 1] - 1))
                                {
                                    minCity = chrome[1];
                                }
                                else
                                {
                                    minCity = chrome[_chromoLength - 1];
                                }
                            }
                            else
                            {
                                if (!bit[chrome[1] - 1])
                                {
                                    minCity = chrome[1];
                                }
                                if (!bit[chrome[_chromoLength - 1] - 1])
                                {
                                    minCity = chrome[_chromoLength - 1];
                                }
                            }
                        }
                        else
                        {
                            if (!bit[chrome[i + 1] - 1] && !bit[chrome[i - 1] - 1])
                            {
                                if (calDistance(currentCity - 1, chrome[i + 1] - 1) < calDistance(currentCity - 1, chrome[i - 1] - 1))
                                {
                                    minCity = chrome[i + 1];
                                }
                                else
                                {
                                    minCity = chrome[i - 1];
                                }
                            }
                            else
                            {
                                if (!bit[chrome[i + 1] - 1])
                                {
                                    minCity = chrome[i + 1];
                                }
                                if (!bit[chrome[i - 1] - 1])
                                {
                                    minCity = chrome[i - 1];
                                }
                            }
                        }
                    }
                    break;
                }// if (chrome[i] == currentCity)
            }//for
            return minCity;
        }

        public int maxNum(int num1, int num2)
        {
            if (num1 > num2)
            {
                return num1;
            }
            else
            {
                return num2;
            }
        }

        public void M_MSCX1(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bitFlag = new bool[_chromoLength];
            int minCity1, minCity2, minIndex;
            float distanceBefore, distanceAfter, minDistance;

            for (int i = 0; i < _chromoLength; i++)
            {
                bitFlag[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);
            child.chromo[0] = this.chromo[0];
            bitFlag[this.chromo[0] - 1] = true;

            for (int i = 1; i < _chromoLength; i++)
            {
                minCity1 = findBeforeAfterCity(child.chromo[i - 1], this.chromo, bitFlag);
                minCity2 = findBeforeAfterCity(child.chromo[i - 1], chromo2.chromo, bitFlag);
         
                minDistance = float.MaxValue;
                minIndex = -1;
                if ((minCity1 == -1) && (minCity2 == -1))
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[this.chromo[j] - 1])
                        {
                            minCity1 = this.chromo[j];
                            break;
                        }
                    }
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[chromo2.chromo[j] - 1])
                        {
                            minCity2 = chromo2.chromo[j];
                            break;
                        }
                    }
                    if (this.calDistance(child.chromo[i - 1] - 1, minCity1 - 1) < this.calDistance(child.chromo[i - 1] - 1, minCity2 - 1))
                    {
                        minIndex = minCity1;
                    }
                    else
                    {
                        minIndex = minCity2;
                    }
                }
                else
                {
                    if ((minCity1 != -1) && (minCity2 != -1))
                    {
                        if (calDistance(child.chromo[i - 1] - 1, minCity1 - 1) < calDistance(child.chromo[i - 1] - 1, minCity2 - 1))
                        {
                            minIndex = minCity1;
                        }
                        else
                        {
                            minIndex = minCity2;
                        }
                    }
                    else
                    {
                        minIndex = maxNum(minCity1, minCity2);
                        //if (minCity1 != -1)
                        //{
                        //    minIndex = minCity1;
                        //}
                        //if (minCity2 != -1)
                        //{
                        //    minIndex = minCity2;
                        //}
                    }
                }
                
                child.chromo[i] = minIndex;
                bitFlag[minIndex - 1] = true;

                //if (nextCt1 == 0 || bitFlag[nextCt1 - 1])
                //{
                //    nextCt1 = findMinCity(child.chromo[i - 1], this.chromo, bitFlag);
                //}
                //if (nextCt2 == 0 || bitFlag[nextCt2 - 1])
                //{
                //    nextCt2 = findMinCity(child.chromo[i - 1], chromo2.chromo, bitFlag);
                //}

                //if (calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                //{
                //    child.chromo[i] = nextCt1;
                //    bitFlag[nextCt1 - 1] = true;
                //}
                //else
                //{
                //    child.chromo[i] = nextCt2;
                //    bitFlag[nextCt2 - 1] = true;
                //}
            }//for


        }

        public void M_MSCX1_1(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bitFlag = new bool[_chromoLength];
            int minCity1, minCity2, minIndex;         

            for (int i = 0; i < _chromoLength; i++)
            {
                bitFlag[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);
            child.chromo[0] = this.chromo[0];
            bitFlag[this.chromo[0] - 1] = true;

            for (int i = 1; i < _chromoLength; i++)
            {
                minCity1 = findBeforeAfterCity1(child.chromo[i - 1], this.chromo, bitFlag);
                minCity2 = findBeforeAfterCity1(child.chromo[i - 1], chromo2.chromo, bitFlag);
                minIndex = -1;
                if (minCity1 == -1)
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[this.chromo[j] - 1])
                        {
                            minCity1 = this.chromo[j];
                            break;
                        }
                    }
                }
                if (minCity2 == -1)
                {                   
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[chromo2.chromo[j] - 1])
                        {
                            minCity2 = chromo2.chromo[j];
                            break;
                        }
                    }
                }
                if (this.calDistance(child.chromo[i - 1] - 1, minCity1 - 1) < this.calDistance(child.chromo[i - 1] - 1, minCity2 - 1))
                {
                    minIndex = minCity1;
                }
                else
                {
                    minIndex = minCity2;
                }
                child.chromo[i] = minIndex;
                bitFlag[minIndex - 1] = true;
            }//for
        }

        //Crossover: find before and after the current city
        //method find before and after the current city, if before city is after city then select it.
        public int countNumber(int[] orinArray, int coutNum)
        {
            int count = orinArray.Where(x => x == coutNum).Count();
            return count;
        }

        public int findBeforeAfterCityWithKeepCommontCity(int currentCity, int[] chrome, bool[] bit)
        {
            int minCity = -1;
            byte indexArr = 0;
            int[] arrCity = new int[4];
            for (int i = 0; i < _chromoLength; i++)
            {
                if (chrome[i] == currentCity)
                {
                    if (i == _chromoLength - 1)
                    {
                        if (!bit[chrome[_chromoLength - 2] - 1])
                        {
                            arrCity[indexArr]  = chrome[_chromoLength - 2];
                            indexArr++;
                        }
                    }
                    else
                    {
                        if (i == 0)
                        {
                            if (!bit[chrome[1] - 1] && !bit[chrome[_chromoLength - 1] - 1])
                            {
                                arrCity[indexArr] = chrome[1];
                                indexArr++;
                                arrCity[indexArr] = chrome[_chromoLength - 1];
                                indexArr++;
                            }
                            else
                            {
                                if (!bit[chrome[1] - 1])
                                {
                                    arrCity[indexArr] = chrome[1];
                                    indexArr++;
                                }
                                if (!bit[chrome[_chromoLength - 1] - 1])
                                {
                                    arrCity[indexArr] = chrome[_chromoLength - 1];
                                    indexArr++;
                                }
                            }
                        }
                        else
                        {
                            if (!bit[chrome[i + 1] - 1] && !bit[chrome[i - 1] - 1])
                            {
                                arrCity[indexArr] = chrome[i + 1];
                                indexArr++;
                                arrCity[indexArr] = chrome[i - 1];
                                indexArr++;
                            }
                            else
                            {
                                if (!bit[chrome[i + 1] - 1])
                                {
                                    arrCity[indexArr] = chrome[i + 1];
                                    indexArr++;
                                }
                                if (!bit[chrome[i - 1] - 1])
                                {
                                    arrCity[indexArr] = chrome[i - 1];
                                    indexArr++;
                                }
                            }
                        }
                    }
                    break;
                }//if
            }//for
            if (indexArr >= 2)
            {
                for (int ii = 0; ii < indexArr - 1; ii++)
                {
                    if (countNumber(arrCity, arrCity[ii]) >= 2)
                    {
                        minCity = arrCity[ii];
                        break;
                    }
                }
                minCity = arrCity[0];
                for (int ii = 1; ii < indexArr; ii++)
                {
                    if (calDistance(currentCity - 1, minCity - 1) > calDistance(currentCity - 1, arrCity[ii] - 1))
                    {
                        minCity = arrCity[ii];
                    }
                }
            }
            else
            {
                if (indexArr > 0)
                {
                    minCity = arrCity[0];
                }
            }

            return minCity;
        }

        public void M_MSCX2(Chromosome chromo2, out Chromosome child, Random ran)
        {
            bool[] bitFlag = new bool[_chromoLength];
            int minCity1, minCity2, minIndex;
            float distanceBefore, distanceAfter, minDistance;

            for (int i = 0; i < _chromoLength; i++)
            {
                bitFlag[i] = false;
            }

            child = new Chromosome(InOutData.NumOfCity);
            child.chromo[0] = this.chromo[0];
            bitFlag[this.chromo[0] - 1] = true;

            for (int i = 1; i < _chromoLength; i++)
            {
                minCity1 = findBeforeAfterCityWithKeepCommontCity(child.chromo[i - 1], this.chromo, bitFlag);
                minCity2 = findBeforeAfterCityWithKeepCommontCity(child.chromo[i - 1], chromo2.chromo, bitFlag);

                minDistance = float.MaxValue;
                minIndex = -1;
                if ((minCity1 == -1) && (minCity2 == -1))
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[this.chromo[j] - 1])
                        {
                            minCity1 = this.chromo[j];
                            break;
                        }
                    }
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag[chromo2.chromo[j] - 1])
                        {
                            minCity2 = chromo2.chromo[j];
                            break;
                        }
                    }
                    if (this.calDistance(child.chromo[i - 1] - 1, minCity1 - 1) < this.calDistance(child.chromo[i - 1] - 1, minCity2 - 1))
                    {
                        minIndex = minCity1;
                    }
                    else
                    {
                        minIndex = minCity2;
                    }
                }
                else
                {
                    if ((minCity1 != -1) && (minCity2 != -1))
                    {
                        if (calDistance(child.chromo[i - 1] - 1, minCity1 - 1) < calDistance(child.chromo[i - 1] - 1, minCity2 - 1))
                        {
                            minIndex = minCity1;
                        }
                        else
                        {
                            minIndex = minCity2;
                        }
                    }
                    else
                    {
                        minIndex = maxNum(minCity1, minCity2);
                     
                    }
                }

                child.chromo[i] = minIndex;
                bitFlag[minIndex - 1] = true;

            }//for


        }

        #region crossover: using list of city have min distance of each city
            //find city in list
            private int findNextCityInList(List<int> lstCt, bool[] flatUse)
            {
                int rCt = -1;
                if (lstCt.Count > 0)
                {
                    foreach (int e in lstCt)
                    {
                        if (!flatUse[e - 1])
                        {
                            rCt = e;
                            break;
                        }
                    }
                }
                else
                {
                    return -1;
                }
                return rCt;
            }
            
            public void M_MSCX3(Chromosome chromo2, out Chromosome child, Random ran, List<int>[] lstCity)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        nextCt1 = findNextCityInList(lstCity[child.chromo[i - 1] - 1], bit);
                        if (nextCt1 == -1)
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[this.chromo[j] - 1])
                                {
                                    nextCt1 = this.chromo[j];
                                    break;
                                }
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        nextCt2 = findNextCityInList(lstCity[child.chromo[i - 1] - 1], bit);
                        if (nextCt2 == -1)
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[chromo2.chromo[j] - 1])
                                {
                                    nextCt2 = chromo2.chromo[j];
                                    break;
                                }
                            }
                        }
                       
                    }
                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                        if (!lstCity[child.chromo[i - 1] - 1].Contains(nextCt1))
                        {
                            lstCity[child.chromo[i - 1] - 1].Add(nextCt1);
                        }
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                        if (!lstCity[child.chromo[i - 1] - 1].Contains(nextCt2))
                        {
                            lstCity[child.chromo[i - 1] - 1].Add(nextCt2);
                        }
                    }
                }//for


            }

        #endregion

        #region crossover: using the city have smallest distance to current city
            public void M_MSCX4(Chromosome chromo2, out Chromosome child, Random ran, int[] toCity, float[] bestDistance)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;
                float dis1, dis2;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        if ((toCity[child.chromo[i - 1] - 1] != -1) && (!bit[toCity[child.chromo[i - 1] - 1] - 1]))
                        {
                            nextCt1 = toCity[child.chromo[i - 1] - 1];
                        }
                        else
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[this.chromo[j] - 1])
                                {
                                    nextCt1 = this.chromo[j];
                                    break;
                                }
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        if ((toCity[child.chromo[i - 1] - 1] != -1) && (!bit[toCity[child.chromo[i - 1] - 1] - 1]))
                        {
                            nextCt2 = toCity[child.chromo[i - 1] - 1];
                        }
                        else
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[chromo2.chromo[j] - 1])
                                {
                                    nextCt2 = chromo2.chromo[j];
                                    break;
                                }
                            }
                        }
                    
                    }

                    dis1 = this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1);
                    dis2 = this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1);

                    if (dis1 < dis2)
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                        if (dis1 < bestDistance[child.chromo[i - 1] - 1])
                        {
                            bestDistance[child.chromo[i - 1] - 1] = dis1;
                            toCity[child.chromo[i - 1] - 1] = nextCt1;
                        }
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                        if (dis2 < bestDistance[child.chromo[i - 1] - 1])
                        {
                            bestDistance[child.chromo[i - 1] - 1] = dis2;
                            toCity[child.chromo[i - 1] - 1] = nextCt2;
                        }
                    }
                }//for

            }

            //using best city in list before finding in parents
            public void M_MSCX5(Chromosome chromo2, out Chromosome child, Random ran, int[] toCity, float[] bestDistance)
            {
                bool[] bit = new bool[_chromoLength];
               
                int nextCt1, nextCt2;
                float dis1, dis2;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                  
                    if ((toCity[child.chromo[i - 1] - 1] != -1) && (!bit[toCity[child.chromo[i - 1] - 1] - 1]))
                    {
                        nextCt1 = toCity[child.chromo[i - 1] - 1];
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                       
                    }
                    else
                    {
                        nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                        nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                        if (nextCt1 == 0 || bit[nextCt1 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[this.chromo[j] - 1])
                                {
                                    nextCt1 = this.chromo[j];
                                    break;
                                }
                            }
                        }
                        if (nextCt2 == 0 || bit[nextCt2 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[chromo2.chromo[j] - 1])
                                {
                                    nextCt2 = chromo2.chromo[j];
                                    break;
                                }
                            }
                        }
                        dis1 = this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1);
                        dis2 = this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1);
                        if (dis1 < dis2)
                        {
                            child.chromo[i] = nextCt1;
                            bit[nextCt1 - 1] = true;
                            if (dis1 < bestDistance[child.chromo[i - 1] - 1])
                            {
                                bestDistance[child.chromo[i - 1] - 1] = dis1;
                                toCity[child.chromo[i - 1] - 1] = nextCt1;
                            }
                        }
                        else
                        {
                            child.chromo[i] = nextCt2;
                            bit[nextCt2 - 1] = true;
                            if (dis2 < bestDistance[child.chromo[i - 1] - 1])
                            {
                                bestDistance[child.chromo[i - 1] - 1] = dis2;
                                toCity[child.chromo[i - 1] - 1] = nextCt2;
                            }
                        }
                    }
                }//for


            }//end method


        #endregion

        #region  crossover using the 3 chromo
            public void M_MSCX6(Chromosome Par2, Chromosome Par3, out Chromosome child, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2, nextCt3;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], Par2.chromo);
                    nextCt3 = findNextCity(child.chromo[i - 1], Par3.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[Par2.chromo[j] - 1])
                            {
                                nextCt2 = Par2.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt3 == 0 || bit[nextCt3 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[Par3.chromo[j] - 1])
                            {
                                nextCt3 = Par3.chromo[j];
                                break;
                            }
                        }
                    }



                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt3 - 1))
                        {
                            child.chromo[i] = nextCt1;
                            bit[nextCt1 - 1] = true;
                        }
                        else
                        {
                            child.chromo[i] = nextCt3;
                            bit[nextCt3 - 1] = true;
                        }
                        
                    }
                    else
                    {
                        if (this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt3 - 1))
                        {
                            child.chromo[i] = nextCt2;
                            bit[nextCt2 - 1] = true;
                        }
                        else
                        {
                            child.chromo[i] = nextCt3;
                            bit[nextCt3 - 1] = true;
                        }
                       
                    }
                }//for


            }

            public void M_MSCX6_1(Chromosome Par2, Chromosome Par3, out Chromosome child, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2, nextCt3;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], Par2.chromo);
                    nextCt3 = findNextCity(child.chromo[i - 1], Par3.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[Par2.chromo[j] - 1])
                            {
                                nextCt2 = Par2.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt3 == 0 || bit[nextCt3 - 1])
                    {
                        if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                        {
                            child.chromo[i] = nextCt1;
                            bit[nextCt1 - 1] = true;
                        }
                        else
                        {
                            child.chromo[i] = nextCt2;
                            bit[nextCt2 - 1] = true;
                        }
                    }
                    else
                    {
                        if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                        {
                            if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt3 - 1))
                            {
                                child.chromo[i] = nextCt1;
                                bit[nextCt1 - 1] = true;
                            }
                            else
                            {
                                child.chromo[i] = nextCt3;
                                bit[nextCt3 - 1] = true;
                            }

                        }
                        else
                        {
                            if (this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt3 - 1))
                            {
                                child.chromo[i] = nextCt2;
                                bit[nextCt2 - 1] = true;
                            }
                            else
                            {
                                child.chromo[i] = nextCt3;
                                bit[nextCt3 - 1] = true;
                            }

                        }
                    }



                  
                }//for


            }

        #endregion

        #region using simple closed path
         
            public void M_MSCX7(Chromosome chromo2, out Chromosome child, int[] index, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;
                int posCt = -1;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {

                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                //child.chromo[0] = this.chromo[0];
                //bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                    posCt = -1;
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (index[j] + 1 == child.chromo[i - 1])
                            {
                                posCt = j;
                                break;
                            }                           
                        }
                        bool ok = true;
                        for (int j = posCt + 1; j < _chromoLength; j++)
                        {
                             if (!bit[index[j]])
                             {
                                 nextCt1 = index[j] + 1;
                                 ok = false;
                                 break;
                             }
                        }
                        if (ok)
                        {
                            for (int j = posCt - 1; j >= 0; j--)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt1 = index[j] + 1;
                                    break;
                                }
                            }
                        }
                     
                        //for (int j = 0; j < _chromoLength; j++)
                        //{
                        //    if (!bit[this.chromo[j] - 1])
                        //    {
                        //        nextCt1 = this.chromo[j];
                        //        break;
                        //    }
                        //}
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        if (posCt == -1)
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (index[j] + 1 == child.chromo[i - 1])
                                {
                                    posCt = j;
                                    break;
                                }
                            }
                        }
                       
                        bool ok = true;
                        for (int j = posCt + 1; j < _chromoLength; j++)
                        {
                            if (!bit[index[j]])
                            {
                                nextCt2 = index[j] + 1;
                                ok = false;
                                break;
                            }
                        }
                        if (ok)
                        {
                            for (int j = posCt - 1; j >= 0; j--)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt2 = index[j] + 1;
                                    break;
                                }
                            }
                        }
                        //for (int j = 0; j < _chromoLength; j++)
                        //{
                        //    if (!bit[chromo2.chromo[j] - 1])
                        //    {
                        //        nextCt2 = chromo2.chromo[j];
                        //        break;
                        //    }
                        //}
                    }
                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for


            }

            public void M_MSCX7_1(Chromosome chromo2, out Chromosome child, int[] index, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;
                int posCt = -1;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {

                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                //child.chromo[0] = this.chromo[0];
                //bit[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                    posCt = -1;
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (index[j] + 1 == child.chromo[i - 1])
                            {
                                posCt = j;
                                break;
                            }
                        }
                        bool ok = true;
                        for (int j = posCt + 1; j < _chromoLength; j++)
                        {
                            if (!bit[index[j]])
                            {
                                nextCt1 = index[j] + 1;
                                ok = false;
                                break;
                            }
                        }
                        if (ok)
                        {
                            for (int j = posCt - 1; j >= 0; j--)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt1 = index[j] + 1;
                                    break;
                                }
                            }
                        }

                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        if (posCt == -1)
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (index[j] + 1 == child.chromo[i - 1])
                                {
                                    posCt = j;
                                    break;
                                }
                            }
                        }

                        bool ok = true;
                        for (int j = posCt + 1; j < _chromoLength; j++)
                        {
                            if (!bit[index[j]])
                            {
                                nextCt2 = index[j] + 1;
                                ok = false;
                                break;
                            }
                        }
                                          
                        if (ok)
                        {
                            for (int j = posCt - 1; j >= 0; j--)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt2 = index[j] + 1;
                                    break;
                                }
                            }
                          
                        }
                      
                    }
                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for


            }

            public void M_MSCX7_2(Chromosome chromo2, out Chromosome child, int[] index, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;
                int posCt = -1;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                    //Console.WriteLine("this");
                }
                else
                {
                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }


                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                    posCt = -1;
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (index[j] + 1 == child.chromo[i - 1])
                            {
                                posCt = j;
                                break;
                            }
                        }
                        bool ok = true;

                        for (int j = posCt + 1; j < _chromoLength; j++)
                        {
                            if (!bit[index[j]])
                            {
                                nextCt1 = index[j] + 1;
                                ok = false;
                                break;
                            }
                        }

                        if (ok)
                        {
                            for (int j = posCt - 1; j >= 0; j--)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt1 = index[j] + 1;
                                    break;
                                }
                            }
                        }
                    }

                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt2 = this.chromo[j];
                                break;
                            }
                        }
                    }//  if (nextCt2 == 0 || bit[nextCt2 - 1])

                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for

            }

            public void M_MSCX7_3(Chromosome chromo2, out Chromosome child, int[] index, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;
                int posCt = -1;
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                    //Console.WriteLine("this");
                }
                else
                {
                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                bool ok;
                int positionInPath = 0;
                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);
                    posCt = -1;
                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (index[j] + 1 == child.chromo[i - 1])
                            {
                                posCt = j;
                                break;
                            }
                        }

                        ok = true;

                        positionInPath = posCt + 1 + _chromoLength;
                        positionInPath = positionInPath % _chromoLength;
                        if (!bit[index[positionInPath]])
                        {
                            nextCt1 = index[positionInPath] + 1;
                            ok = false;
                        }

                        if (ok)
                        {
                            positionInPath = posCt - 1 + _chromoLength;
                            positionInPath = positionInPath % _chromoLength;
                            if (!bit[index[positionInPath]])
                            {
                                nextCt1 = index[positionInPath] + 1;
                                ok = false;
                            }
                        }

                        if (ok)
                        {
                            for (int j = posCt + 2; j < _chromoLength; j++)
                            {
                                if (!bit[index[j]])
                                {
                                    nextCt1 = index[j] + 1;
                                    ok = false;
                                    break;
                                }
                            }

                            if (ok)
                            {
                                for (int j = posCt - 2; j >= 0; j--)
                                {
                                    if (!bit[index[j]])
                                    {
                                        nextCt1 = index[j] + 1;
                                        break;
                                    }
                                }
                            }
                        }
                    }

                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt2 = this.chromo[j];
                                break;
                            }
                        }
                        //for (int j = 0; j < _chromoLength; j++)
                        //{
                        //    if (!bit[this.chromo[j] - 1])
                        //    {
                        //        nextCt2 = this.chromo[j];
                        //        break;
                        //    }
                        //}
                        //nextCt21 = nextCt2;
                        //for (int j = 0; j < _chromoLength; j++)
                        //{
                        //    if (!bit[chromo2.chromo[j] - 1])
                        //    {
                        //        nextCt21 = chromo2.chromo[j];
                        //        break;
                        //    }
                        //}

                        //if (this.calDistance(child.chromo[i - 1] - 1, nextCt21 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                        //{
                        //    nextCt2 = nextCt21;
                        //}
                        

                    }//  if (nextCt2 == 0 || bit[nextCt2 - 1])


                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for


            }


        #endregion

        #region  Linear Distance
            //crossover use linear distance
            public void linearDistanceCrossover(Chromosome chromo2, out Chromosome child, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {
                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                float maxDistance, totalDis1, totalDis2, tempDis1, tempDis2;
                int c1, c2;
                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }
                    tempDis1 = this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1);
                    tempDis2 = this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1);
                    maxDistance = Math.Max(tempDis1, tempDis2);


                    if ((findNextCity(nextCt1, this.chromo) == 0) || bit[findNextCity(nextCt1, this.chromo) - 1])
                    {
                        c1 = 1;
                    }
                    else
                    {
                        c1 = 0;
                    }

                    if ((findNextCity(nextCt2, chromo2.chromo) == 0) || bit[findNextCity(nextCt2, chromo2.chromo) - 1])
                    {
                        c2 = 1;
                    }
                    else
                    {
                        c2 = 0;
                    }
                    totalDis1 = (float)((tempDis1 / maxDistance) * 0.8 + c1 * 0.2);
                    totalDis2 = (float)(tempDis2 / maxDistance * 0.8 + c2 * 0.2);
                    if (totalDis1 < totalDis2)
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for


            }

            //find next city for linear distace
            private void findNextCity(int city, int[] tour, bool[] visited, ref bool ctVisisted, ref int nextCity)
            {
                nextCity = 0;
                ctVisisted = false;
                for (int i = 0; i < _chromoLength; i++)
                {
                    if (tour[i] == city)
                    {
                        if (i == _chromoLength - 1)
                        {
                            ctVisisted = true;
                        }
                        else
                        {
                            if (visited[tour[i + 1] - 1])
                            {
                                ctVisisted = true;
                            }
                        }
                        if (ctVisisted)
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if ((!visited[tour[j] - 1]) && (tour[j] != city))
                                {
                                    nextCity = tour[j];
                                    return;
                                }
                            }
                        }
                        else
                        {
                            nextCity = tour[i + 1];
                            return;
                        }
                    }
                }

            }

            private float max2(float c1, float c2)
            {
                if (c1 < c2)
                {
                    return c2;
                }
                else
                {
                    return c1;
                }
            }

            private float max4(float c1, float c2, float c3, float c4)
            {
                return Math.Max(Math.Max(c1, c2), Math.Max(c3, c4));
            }

            //ham tinh so sanh khoang cach thanh pho co tinh voi viec thanh pho tiep theo ko co hoac da duoc chon
            private float minBeta(int currentCt, ref int ct1, bool vs1, ref int ct2, bool vs2, float beta)
            {
                float tempDis1 = this.calDistance(currentCt - 1, ct1 - 1);
                float tempDis2 = this.calDistance(currentCt - 1, ct2 - 1);
                if (vs1)
                {
                    tempDis1 = tempDis1 * beta;
                }
                if (vs2)
                {
                    tempDis2 = tempDis2 * beta;
                }
                if (tempDis1 < tempDis2)
                {
                    return tempDis1;
                }
                else
                {
                    int temp = ct1;
                    ct1 = ct2;
                    ct2 = temp;
                    return tempDis2;
                }

            }

            //alpha is costant for
            //beta is constant for 
            public void linearDistanceCrossover1(Chromosome chromo2, out Chromosome child, Random ran, float alpha1, float alpha2, float beta)
            {
                bool[] bit = new bool[_chromoLength];
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }
                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {
                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                float totalDis1, totalDis2;
                bool ctVs1 = false;
                bool ctVs2 = false;
                int nextCt1 = 0;
                int nextCt2 = 0;
                int cityTemp1 = 0;
                int cityTemp2 = 0;
                bool cityVisTemp1 = false;
                bool cityVisTemp2 = false;
                for (int i = 1; i < _chromoLength; i++)
                {
                    if (i < _chromoLength - 1)
                    {
                        //tinh truong hop 1
                        findNextCity(child.chromo[i - 1], this.chromo, bit, ref ctVs1, ref nextCt1);
                        findNextCity(nextCt1, this.chromo, bit, ref cityVisTemp1, ref cityTemp1);
                        findNextCity(nextCt1, chromo2.chromo, bit, ref cityVisTemp2, ref cityTemp2);
                        totalDis1 = this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1);
                        if (ctVs1)
                        {
                            totalDis1 = totalDis1 * beta;
                        }
                        totalDis1 = totalDis1 * alpha1 + minBeta(nextCt1, ref cityTemp1, cityVisTemp1, ref cityTemp2, cityVisTemp2, beta) * alpha2;
                        //tinh truong hop 2
                        findNextCity(child.chromo[i - 1], chromo2.chromo, bit, ref ctVs2, ref nextCt2);
                        findNextCity(nextCt2, this.chromo, bit, ref cityVisTemp1, ref cityTemp1);
                        findNextCity(nextCt2, chromo2.chromo, bit, ref cityVisTemp2, ref cityTemp2);
                        totalDis2 = this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1);
                        if (ctVs2)
                        {
                            totalDis2 = totalDis2 * beta;
                        }
                        totalDis2 = totalDis2 * alpha1 + minBeta(nextCt2, ref cityTemp1, cityVisTemp1, ref cityTemp2, cityVisTemp2, beta) * alpha2;

                        if (totalDis1 < totalDis2)
                        {
                            child.chromo[i] = nextCt1;
                            bit[nextCt1 - 1] = true;
                        }
                        else
                        {
                            child.chromo[i] = nextCt2;
                            bit[nextCt2 - 1] = true;
                        }
                    }
                    else
                    {
                        nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                        nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                        if (nextCt1 == 0 || bit[nextCt1 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[this.chromo[j] - 1])
                                {
                                    nextCt1 = this.chromo[j];
                                    break;
                                }
                            }
                        }
                        if (nextCt2 == 0 || bit[nextCt2 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[chromo2.chromo[j] - 1])
                                {
                                    nextCt2 = chromo2.chromo[j];
                                    break;
                                }
                            }
                        }
                        if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                        {
                            child.chromo[i] = nextCt1;
                            bit[nextCt1 - 1] = true;
                        }
                        else
                        {
                            child.chromo[i] = nextCt2;
                            bit[nextCt2 - 1] = true;
                        }
                    }//if - else

                   
                }//for

            }

            public void linearDistanceCrossover2(Chromosome chromo2, out Chromosome child, Random ran, float alpha1, float alpha2, float beta)
            {
                bool[] bit = new bool[_chromoLength];
                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }
                child = new Chromosome(InOutData.NumOfCity);

                if (this._fitness < chromo2._fitness)
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {
                    child.chromo[0] = chromo2.chromo[0];
                    bit[chromo2.chromo[0] - 1] = true;
                }
                float totalDis1, totalDis2;
                bool ctVs1 = false;
                bool ctVs2 = false;
                int nextCt1 = 0;
                int nextCt2 = 0;
                int cityTemp1 = 0;
                int cityTemp2 = 0;
                int cityTemp3 = 0;
                int cityTemp4 = 0;
                bool cityVisTemp1 = false;
                bool cityVisTemp2 = false;
                int ii = 1;
                while (ii <= _chromoLength - 1)
                {
                    if (ii < _chromoLength - 2)
                    {
                        //tinh truong hop 1
                        findNextCity(child.chromo[ii - 1], this.chromo, bit, ref ctVs1, ref nextCt1);
                        findNextCity(nextCt1, this.chromo, bit, ref cityVisTemp1, ref cityTemp1);
                        findNextCity(nextCt1, chromo2.chromo, bit, ref cityVisTemp2, ref cityTemp2);
                        totalDis1 = this.calDistance(child.chromo[ii - 1] - 1, nextCt1 - 1);
                        if (ctVs1)
                        {
                            totalDis1 = totalDis1 * beta;
                        }
                        totalDis1 = totalDis1 * alpha1 + minBeta(nextCt1, ref cityTemp1, cityVisTemp1, ref cityTemp2, cityVisTemp2, beta) * alpha2;

                        //tinh truong hop 2
                        findNextCity(child.chromo[ii - 1], chromo2.chromo, bit, ref ctVs2, ref nextCt2);
                        findNextCity(nextCt2, this.chromo, bit, ref cityVisTemp1, ref cityTemp3);
                        findNextCity(nextCt2, chromo2.chromo, bit, ref cityVisTemp2, ref cityTemp4);
                        totalDis2 = this.calDistance(child.chromo[ii - 1] - 1, nextCt2 - 1);
                        if (ctVs2)
                        {
                            totalDis2 = totalDis2 * beta;
                        }
                        totalDis2 = totalDis2 * alpha1 + minBeta(nextCt2, ref cityTemp3, cityVisTemp1, ref cityTemp4, cityVisTemp2, beta) * alpha2;

                        if (totalDis1 < totalDis2)
                        {
                            child.chromo[ii] = nextCt1;
                            bit[nextCt1 - 1] = true;
                            ii++;
                            child.chromo[ii] = cityTemp1;
                            bit[cityTemp1 - 1] = true;
                            ii++;
                        }
                        else
                        {
                            child.chromo[ii] = nextCt2;
                            bit[nextCt2 - 1] = true;
                            ii++;
                            child.chromo[ii] = cityTemp3;
                            bit[cityTemp3 - 1] = true;
                            ii++;
                        }
                    }
                    else
                    {
                        nextCt1 = findNextCity(child.chromo[ii - 1], this.chromo);
                        nextCt2 = findNextCity(child.chromo[ii - 1], chromo2.chromo);

                        if (nextCt1 == 0 || bit[nextCt1 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[this.chromo[j] - 1])
                                {
                                    nextCt1 = this.chromo[j];
                                    break;
                                }
                            }
                        }
                        if (nextCt2 == 0 || bit[nextCt2 - 1])
                        {
                            for (int j = 0; j < _chromoLength; j++)
                            {
                                if (!bit[chromo2.chromo[j] - 1])
                                {
                                    nextCt2 = chromo2.chromo[j];
                                    break;
                                }
                            }
                        }
                        if (this.calDistance(child.chromo[ii - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[ii - 1] - 1, nextCt2 - 1))
                        {
                            child.chromo[ii] = nextCt1;
                            bit[nextCt1 - 1] = true;                            
                        }
                        else
                        {
                            child.chromo[ii] = nextCt2;
                            bit[nextCt2 - 1] = true;
                        }
                        ii++;
                    }//if - else


                }//while

            }
        #endregion

        #region crossover with radius = 1, 2, 3,..
            //find next city with radius
            //return city has min distance 
            private int findNextCityWithRadius(int currentCity, int[] tour, bool[] ctVisited, int radius)
            {
                int t = 0;
                float minDistance = float.MaxValue;
                float temp = 0;
                int[] cities = new int[radius];               
                int index = 0;
                for (int i = 0; i < _chromoLength; i++)
                {
                    if (tour[i] == currentCity)
                    {
                        for (int j = 1; j <= radius; j++)
                        {
                            index = (i + j) % _chromoLength;
                            if (!ctVisited[tour[index] - 1])
                            {
                                temp = this.calDistance(currentCity - 1, tour[index] - 1);
                                if (minDistance > temp)
                                {
                                    minDistance = temp;
                                    t = tour[index];
                                }
                            }
                        }
                        break;
                    }
                }
                return t;
            }

          
            //Crossover: using radius from current city
            public void MSCX_Radius(Chromosome chromo2, out Chromosome child, Random ran, int radius)
            {
                bool[] bitFlag = new bool[_chromoLength];
                int nextCt1, nextCt2;             
                int minCity1, minCity2;
             
                for (int i = 0; i < _chromoLength; i++)
                {
                    bitFlag[i] = false;
                }

                child = new Chromosome(InOutData.NumOfCity);
                child.chromo[0] = this.chromo[0];
                bitFlag[this.chromo[0] - 1] = true;

                for (int i = 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCityWithRadius(child.chromo[i - 1], this.chromo, bitFlag, radius);                    
                    if (nextCt1 == 0)
                    {
                        nextCt1 = findMinCity(child.chromo[i - 1], this.chromo, bitFlag);
                    }
                    nextCt2 = findNextCityWithRadius(child.chromo[i - 1], chromo2.chromo, bitFlag, radius);
                    if (nextCt2 == 0)
                    {
                        nextCt2 = findMinCity(child.chromo[i - 1], chromo2.chromo, bitFlag);
                    }

                    if (calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bitFlag[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bitFlag[nextCt2 - 1] = true;
                    }
                }//for


            }

        #endregion

        #region HybridizingCrossover
            //Return one child
            public void hybridizingCrossover(Chromosome chromo2, out Chromosome child, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1 = 0;
                int nextCt2 = 0;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }
                child = new Chromosome(InOutData.NumOfCity);

                int pos1 = ran.Next(1, _chromoLength - 1);
                int pos2 = ran.Next(_chromoLength - pos1) + pos1;
                for (int i = pos1; i <= pos2; i++)
                {
                    child.chromo[i] = chromo2.chromo[i];
                    bit[child.chromo[i] - 1] = true;
                }

                if (!bit[this.chromo[0] - 1])
                {
                    child.chromo[0] = this.chromo[0];
                    bit[this.chromo[0] - 1] = true;
                }
                else
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bit[this.chromo[j] - 1])
                        {
                            nextCt1 = this.chromo[j];
                            break;
                        }
                    }
                    child.chromo[0] = nextCt1;
                    bit[nextCt1 - 1] = true;
                }                            

                for (int i = 1; i < pos1; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for
                for (int i = pos2 + 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                }//for


            }

            //Return two child
            public void hybridizingCrossover1(Chromosome chromo2, out Chromosome child1, out Chromosome child2, Random ran)
            {
                bool[] bitFlag1 = new bool[_chromoLength];
                bool[] bitFlag2 = new bool[_chromoLength];
                int nextCt1 = 0;
                int nextCt2 = 0;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bitFlag1[i] = false;
                    bitFlag2[i] = false;
                }
                child1 = new Chromosome(InOutData.NumOfCity);
                child2 = new Chromosome(InOutData.NumOfCity);

                int pos1 = ran.Next(1, _chromoLength - 1);
                int pos2 = ran.Next(_chromoLength - pos1) + pos1;

                for (int i = pos1; i <= pos2; i++)
                {
                    child1.chromo[i] = chromo2.chromo[i];
                    bitFlag1[child1.chromo[i] - 1] = true;

                    child2.chromo[i] = this.chromo[i];
                    bitFlag2[child2.chromo[i] - 1] = true;
                }

                if (!bitFlag1[this.chromo[0] - 1])
                {
                    child1.chromo[0] = this.chromo[0];
                    bitFlag1[this.chromo[0] - 1] = true;
                }
                else
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag1[this.chromo[j] - 1])
                        {
                            nextCt1 = this.chromo[j];
                            break;
                        }
                    }
                    child1.chromo[0] = nextCt1;
                    bitFlag1[nextCt1 - 1] = true;
                }

                if (!bitFlag2[chromo2.chromo[0] - 1])
                {
                    child2.chromo[0] = chromo2.chromo[0];
                    bitFlag2[child2.chromo[0] - 1] = true;
                }
                else
                {
                    for (int j = 0; j < _chromoLength; j++)
                    {
                        if (!bitFlag2[chromo2.chromo[j] - 1])
                        {
                            nextCt2 = chromo2.chromo[j];
                            break;
                        }
                    }
                    child2.chromo[0] = nextCt2;
                    bitFlag2[nextCt2 - 1] = true;
                }

                

                for (int i = 1; i < pos1; i++)
                {
                    nextCt1 = findNextCity(child1.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child1.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bitFlag1[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag1[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bitFlag2[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag2[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child1.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child1.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child1.chromo[i] = nextCt1;
                        bitFlag1[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child1.chromo[i] = nextCt2;
                        bitFlag1[nextCt2 - 1] = true;
                    }
                    //child 2
                    nextCt1 = findNextCity(child2.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child2.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bitFlag2[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag2[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bitFlag2[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag2[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child2.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child2.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child2.chromo[i] = nextCt1;
                        bitFlag2[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child2.chromo[i] = nextCt2;
                        bitFlag2[nextCt2 - 1] = true;
                    }



                }//for
                for (int i = pos2 + 1; i < _chromoLength; i++)
                {
                    nextCt1 = findNextCity(child1.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child1.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bitFlag1[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag1[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bitFlag1[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag1[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child1.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child1.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child1.chromo[i] = nextCt1;
                        bitFlag1[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child1.chromo[i] = nextCt2;
                        bitFlag1[nextCt2 - 1] = true;
                    }
                    //child 2
                    nextCt1 = findNextCity(child2.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child2.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bitFlag2[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag2[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bitFlag2[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bitFlag2[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child2.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child2.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child2.chromo[i] = nextCt1;
                        bitFlag2[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child2.chromo[i] = nextCt2;
                        bitFlag2[nextCt2 - 1] = true;
                    }



                }//for


            }
        #endregion
            //mscx create two children
            public void MSCX_TwoChildren(Chromosome chromo2, out Chromosome child1, out Chromosome child2, Random ran)
            {
                bool[] bit = new bool[_chromoLength];
                int nextCt1, nextCt2;

                for (int i = 0; i < _chromoLength; i++)
                {
                    bit[i] = false;
                }

                child1 = new Chromosome(InOutData.NumOfCity);
                child2 = new Chromosome(InOutData.NumOfCity);
                child1.chromo[0] = this.chromo[0];
                bit[this.chromo[0] - 1] = true;
                child2.chromo[0] = chromo2.chromo[0];
                bit[chromo2.chromo[0] - 1] = true;

             
                for (int i = 1; i < _chromoLength; i++)
                {
                    //children 1
                    nextCt1 = findNextCity(child1.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child1.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child1.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child1.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child1.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child1.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }
                    //children 2
                    nextCt1 = findNextCity(child2.chromo[i - 1], this.chromo);
                    nextCt2 = findNextCity(child2.chromo[i - 1], chromo2.chromo);

                    if (nextCt1 == 0 || bit[nextCt1 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[this.chromo[j] - 1])
                            {
                                nextCt1 = this.chromo[j];
                                break;
                            }
                        }
                    }
                    if (nextCt2 == 0 || bit[nextCt2 - 1])
                    {
                        for (int j = 0; j < _chromoLength; j++)
                        {
                            if (!bit[chromo2.chromo[j] - 1])
                            {
                                nextCt2 = chromo2.chromo[j];
                                break;
                            }
                        }
                    }

                    if (this.calDistance(child2.chromo[i - 1] - 1, nextCt1 - 1) < this.calDistance(child2.chromo[i - 1] - 1, nextCt2 - 1))
                    {
                        child2.chromo[i] = nextCt1;
                        bit[nextCt1 - 1] = true;
                    }
                    else
                    {
                        child2.chromo[i] = nextCt2;
                        bit[nextCt2 - 1] = true;
                    }

                }//for


            }

            public void PMX(Chromosome chromo2, out Chromosome child1, out Chromosome child2, Random ran)
            {
                child1 = new Chromosome(InOutData.NumOfCity);
                child2 = new Chromosome(InOutData.NumOfCity);
                int pos1 = ran.Next(_chromoLength - 1);
                int pos2 = ran.Next(_chromoLength - pos1) + pos1;
                ArrayList s1 = new ArrayList();
                ArrayList s2 = new ArrayList();
                for (int i = pos1; i <= pos2; i++)
                {
                    child1.chromo[i] = chromo2.chromo[i];
                    s1.Add(chromo2.chromo[i]);
                    child2.chromo[i] = this.chromo[i];
                    s2.Add(this.chromo[i]);
                }
                int index1 = 0;             
                int temp = 0;
                for (int i = 0; i < pos1; i++)
                {
                    if (!s1.Contains(this.chromo[i]))
                    {
                        child1.chromo[i] = this.chromo[i];
                    }
                    else
                    {
                        index1 = s1.IndexOf(this.chromo[i]);
                        while (index1 != -1)
                        {
                            temp = (int)s2[index1];
                            index1 = s1.IndexOf(temp);
                        }
                        child1.chromo[i] = temp;
                    }
                    if (!s2.Contains(chromo2.chromo[i]))
                    {
                        child2.chromo[i] = chromo2.chromo[i];
                    }
                    else
                    {
                        index1 = s2.IndexOf(chromo2.chromo[i]);
                        while (index1 != -1)
                        {
                            temp = (int)s1[index1];
                            index1 = s2.IndexOf(temp);
                        }
                        child2.chromo[i] = temp;
                    }
                }
                for (int i = pos2 + 1; i < _chromoLength; i++)
                {
                    if (!s1.Contains(this.chromo[i]))
                    {
                        child1.chromo[i] = this.chromo[i];
                    }
                    else
                    {
                        index1 = s1.IndexOf(this.chromo[i]);
                        while (index1 != -1)
                        {
                            temp = (int)s2[index1];
                            index1 = s1.IndexOf(temp);
                        }
                        child1.chromo[i] = temp;
                    }
                    if (!s2.Contains(chromo2.chromo[i]))
                    {
                        child2.chromo[i] = chromo2.chromo[i];
                    }
                    else
                    {
                        index1 = s2.IndexOf(chromo2.chromo[i]);
                        while (index1 != -1)
                        {
                            temp = (int)s1[index1];
                            index1 = s2.IndexOf(temp);
                        }
                        child2.chromo[i] = temp;
                    }
                }
                //for (int i = 0; i < _chromoLength; i++)
                //{
                //    Console.Write(child1.chromo[i] + " ");
                    
                //}
                //Console.WriteLine();
                //Console.ReadKey();
            }

        #region using intersection of segments
            //function check intersect of segments
            public bool intersectionOfSegments(Point start1, Point end1, Point start2, Point end2)
            {
                double A1 = end1.Y - start1.Y;
                double B1 = start1.X - end1.X;
                double C1 = A1 * start1.X + B1 * start1.Y;

                double A2 = end2.Y - start2.Y;
                double B2 = start2.X - end2.X;
                double C2 = A2 * start2.X + B2 * start2.Y;

                double det = A1*B2 - A2*B1;
                if(det == 0)
                {
                    //Lines are parallel
                    return false;
                }
                else
                {
                    double x = (B2*C1 - B1*C2)/det;
                    double y = (A1 * C2 - A2 * C1) / det;
                    if((Math.Min(start1.X, end1.X) <= x) && (Math.Max(start1.X, end1.X) >= x) && (Math.Min(start1.Y, end1.Y) <= y) && (Math.Max(start1.Y, end1.Y) >= y)
                        && (Math.Min(start2.X, end2.X) <= x) && (Math.Max(start2.X, end2.X) >= x) && (Math.Min(start2.Y, end2.Y) <= y) && (Math.Max(start2.Y, end2.Y) >= y))
                    {
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }

            }

           

        #endregion
    }
}
